import java.util.Map;
import java.util.TreeMap;

/**
 * 729. 我的日程安排表 I
 * https://leetcode-cn.com/problems/my-calendar-i/
 */
public class Solutions_729 {
    public static void main(String[] args) {
        MyCalendar obj = new MyCalendar();
        boolean res1 = obj.book(10, 20);  // output: true
        boolean res2 = obj.book(15, 25);  // output: false
        boolean res3 = obj.book(25, 40);  // output: true
        boolean res4 = obj.book(20, 30);  // output: false
        System.out.println("");
    }
}

class Node_729 {
    int start;
    int end;
    Node_729 left;
    Node_729 right;

    Node_729(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

/**
 * 解法二：线段树思想（16ms）
 */
class MyCalendar {
    Node_729 root;

    public MyCalendar() {
        root = new Node_729(-1, -1);
    }

    public boolean book(int start, int end) {
        Node_729 curNode = new Node_729(start, end);
        Node_729 cur = root;
        while (true) {
            if (end <= cur.start) {
                // [start, end] 区间在 root 区间的左侧
                if (cur.left == null) {
                    // 直接放在 cur 的右侧
                    cur.left = curNode;
                    return true;
                }
                cur = cur.left;
            } else if (start >= cur.end) {
                // [start, end] 区间在 root 区间的右侧
                if (cur.right == null) {
                    // 直接放在 cur 的右侧
                    cur.right = curNode;
                    return true;
                }
                cur = cur.right;
            } else {
                // [start, end] 区间与 root 区间重叠
                return false;
            }
        }
    }
}

/**
 * 解法一：TreeMap（28ms）
 */
class MyCalendar2 {
    // 使用 treeMap 结构
    TreeMap<Integer, Integer> treeMap;

    public MyCalendar2() {
        treeMap = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        // 获取小于 start 的最大值的 entry
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(start);
        if (entry != null && start < entry.getValue()) {
            // 左侧重叠：[15, 20] 与 [10, 20]
            return false;
        }
        // 获取大于 start 的最小值的 entry
        Map.Entry<Integer, Integer> entry1 = treeMap.ceilingEntry(start);
        if (entry1 != null && end > entry1.getKey()) {
            // 左侧重叠：[20, 30] 与 [25, 40]
            return false;
        }
        treeMap.put(start, end);
        return true;
    }
}
